package DataStr.homework03;

import DataStr.ex01.ex05;

import java.util.LinkedList;
import java.util.Queue;

//节点类：根，左孩子右孩子
class TreeNode{
    char val;
    TreeNode lchild;
    TreeNode rchild;
    //重构节点类
    public TreeNode(char data){
        this.val=data;
        this.lchild=null;
        this.rchild=null;
    }
}
public class BinaryTree {
    //创建用来记录序列变换的位置
    private int index;
    //主类，根据先根序列创建二叉树
    public TreeNode BuildTree(String pro){
        return BinaryTreeHelp(pro);
    }
    //辅助递归方法
    public TreeNode BinaryTreeHelp(String pro) {
        //如果序列大于当前字符串长度，则停止
        if(index>=pro.length()){
            return null;
        }
        //取当前字符
        char ch=pro.charAt(index);
        //如果当前字符为 ^，则表示为空，index加一，返回null
        if(pro.charAt(index)=='^'){
            index++;
            return null;
        }
        //创建当前节点
        TreeNode node=new TreeNode(ch);
        //index移动到下一个字符
        index++;
        //递归构建左孩子
        node.lchild=BinaryTreeHelp(pro);
        //递归构建右孩子
        node.rchild=BinaryTreeHelp(pro);
        return node;
    }
    //先根遍历辅助方法
    public void preprint(TreeNode root){
        if(root!=null){
            System.out.print(root.val);
            preprint(root.lchild);
            preprint(root.rchild);
        }
    }
    public void midprint(TreeNode root){
        if(root!=null) {
            midprint(root.lchild);
            System.out.print(root.val);
            midprint(root.rchild);
        }
    }
    public void lastprint(TreeNode root){
        if(root!=null){
            lastprint(root.lchild);
            lastprint(root.rchild);
            System.out.print(root.val);
        }
    }
    //计算该树节点方法
    public int count1(TreeNode root) {
        //采用层次遍历的方式对二叉树进行遍历并计算节点的个数
        int count=0;
        if (root != null) {
            //构建队列
            Queue<TreeNode> L=new LinkedList();
            //根节点入队列
            L.offer(root);
            while(!L.isEmpty()){
                root=L.poll();
            //节点数目加一
                ++count;
            //左孩子不为空，入队列
                if(root.lchild!=null){
                    L.offer(root.lchild);
                }
                if(root.rchild!=null){
                    L.offer(root.rchild);
                }
            //右孩子不为空，入队列
            }
        }
        return count;
    }
    public int count2(TreeNode root){
            //采用先根遍历方式对二叉树进行遍历，计算其节点数目
        int count=0;
        if(root!=null) {
            ++count;
            //根节点加一
            //加上左孩子节点数
            count+=count2(root.lchild);
            //加上右孩子节点数
            count+=count2(root.rchild);
        }
        return count;
        }
        public int height(TreeNode root){
        if(root!=null){
            int height1=height(root.lchild);
            int height2=height(root.rchild);
            return 1+(height1>height2?height1:height2);
        }
        return 0;
        }
    //主方法
    public static void main(String[]args){
        BinaryTree b=new BinaryTree();
        String pro="AB^D^^C^^";
        //构建二叉树
        TreeNode root=b.BuildTree(pro);
        System.out.print("先根遍历结果:");
        b.preprint(root);
        System.out.println("");
        System.out.print("中根遍历结果:");
        b.midprint(root);
        System.out.println("");
        System.out.print("后序遍历结果:");
        b.lastprint(root);
        System.out.println("");
        System.out.print("count1方法得出节点数为:"+b.count1(root));
        System.out.println("");
        System.out.print("count2方法得出节点数为:"+b.count2(root));
        System.out.println("");
        System.out.print("该树的高度为:"+b.height(root));
    }
}
